import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution675 {
    List<Node> list = new ArrayList<Node>() ;
    int[][] arr ;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0} ;
    int m , n ;
    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size() ; n = forest.get(0).size() ;
        arr = new int[m][n] ;
        for(int i=0 ; i < m ;i ++){
            for(int j=0 ; j < n ; j ++){
                arr[i][j] = forest.get(i).get(j) ;
                if(arr[i][j] > 1 ){
                    list.add(new Node(arr[i][j] , i , j)) ;
                }
            }
        }
        if(arr[0][0] == 0) return -1 ;
        list.sort((o1,o2)->o1.val.compareTo(o2.val)) ;
        int sum = 0 ;
        int[] cur = {0,0} ;
        for(Node node : list){
            int[] tar = node.index ;
            int ret = getLen(cur , tar) ;
            if(ret == - 1)return -1 ;
            cur = tar ;
            sum += ret;
        }


        return  sum  ;
    }

    private int getLen(int[] start , int[] target){
        if(start[0] == target[0] && start[1] == target[1]) return 0 ;
        Queue<int[]> queue = new LinkedList<>() ;
        boolean[][] hash = new boolean[m][n] ;
        queue.add(start) ;
        hash[start[0]][start[1]] = true ;
        int len = 0 ;
        while(!queue.isEmpty()){
            len ++ ;
            int size = queue.size() ;
            for(int i=0 ; i <size ; i ++){
                int[] ret  = queue.poll() ;
                int a  = ret[0] , b = ret[1] ;
                for(int j=0 ; j < 4 ; j ++){
                    int x = dx[j]+a , y = dy[j]+b ;
                    if(x >=0 && x <m && y>=0 && y<n && !hash[x][y] && arr[x][y] != 0){
                        queue.add(new int[] {x , y}) ;
                        hash[x][y] = true ;
                    }
                    if(x == target[0] && y == target[1]){
                        return len ;
                    }
                }
            }

        }
        return -1 ;
    }


}

class Node{
    Integer val ;
    int[] index ;

    Node(int val , int x , int y){
        this.val = val ;
        this.index = new int[] {x , y} ;
    }

}